In many technical areas there are difficult optimisation problems, which can only be solved to a very limited extent by an automated technical--mathematical computer treatment. Thus, traditional optimisation systems are often already pushed to their limits in the interpretation of simple telephone, power, water distribution or remote heating networks and deliver inadequate results. Similar problems arise in the numerical control of machine tools, in laying out electronic circuits on one integrated computer chip as well as in drawing up plans for optimal loading of machines--or fleets of vehicles. Particularly complex problems were thus often handled only with intuition and experience, but not with the aid of computers.
Classic processes for the solution--even though it might be of only limited usefulness--of more complex optimisation problems (where "solution" for any problem is to be understood as the solvable "solution" to that problem, but not the "optimal" solution) make use of iterative processes with local change searches. Thus, for example, there is an iterative solution to the problem of finding the shortest connecting route through a given number of places, often of course generally solutions, which are about 10% from the optimum. However, 10% in the case of complex and economically significant optimisation problems like chip placement is a deviation which is fundamentally no longer acceptable.
Different optimization methods in accordance with the state of the art are found in the following articles, which are incorporated herein in their entirety by reference:
a) W. Domschke, "Logistik: Rundreisen und Touren", Munich, Vienna, Oldenbourg, 3rd edition (199); PA0 b) Bachem et al., "Simulated Trading--Eine kurze Einfuhrung", 3. Workshop Parallele Systeme und Algorithmen, Bonn l./2. April 1993, pp.81-87; PA0 c) Dueck et al., "Threshold Accepting; A General Purpose Optimization Algorithm Appearing superior to Simulated Annealing", Journal of Comp. Physics, Vol. 9, pp. 161-165, 199; PA0 d) M. Bargl "Akzeptanz und Effizienz computergestutzter Dispositionssysteme in der Transportwirtschaft", Verlag "Peter Lang".
According to DUECK et al., optimisation problems with a technical background can be formulated in mathematical language as follows: Given a number X of states x (or "solutions"). Since the states have a kind of geometric mutual relationship--one can describe two very similar ones as narrowly adjacent, two very different ones as remote -, X is also called a space of states. In this space a real value target function f is defined. That is to say: For each state x from the space X a real number f (x) can be calculated, which should represent a measure of the quality of x: for example f (x) can be the length of a tour x or the number of parts in a knapsack with the package x. Optimize means: look for a state x in the space X, for which f (x) is minimal (as in the Travelling Salesman problem) or maximum (as in the knapsack problem). Since minimizing f means the same as maximizing -f, only a theory for maximizing is necessary (cf. also: "Optimieren mit Evolutionsstrategien" by Paul Ablay, Spektrum der Wissenschaft, July 1987, page 14).
It is generally usual, for the solution of scheduling problems, such as the Travelling Salesman problem, to use iterative processes with local change search, where the search for a good solution starts with any solution, for example, a spontaneously selected round tour. An optimizing computer changes this and checks, whether the new solution is better (shorter). If so, the optimizing computer replaces the old tour by the new and checks again: Can it be changed around, so that an even better solution results? If it succeeds in doing so, it continues working with this solution, until the solution found can no longer be improved by changing it locally (local optimum or minimum). Such iteration methods can become very complicated even in local extrema, without getting sufficiently close to an overall extremum.
A clear improvement over the classical optimizing method results from the processes developed by DUECK et al., "Threshold Accepting (TA)" and "flood". This is an optimizing method, which relates to an iteration which also permits worsened states, within the framework of a tolerance threshold T.
If T is large, almost all solutions are allowed, regardless of whether they improve the instant solution or make it worse. During the course of the process, however, T is gradually reduced to ZERO. Thus with large T, the solution is already involved in the region of good solutions and then, through a reduction in T, approaches the overall extremum, that is, the very best solution, ever more rapidly. In the vicinity of the absolute extremum the rule applies more frequently; there a step is often prohibited. The maintenance of ever reducing thresholds drives the solution closer to a very good or optimal solution. If, finally, T=0, the algorithm corresponds to an iteration which will permit of no worsening of the solution. One great advantage of this method resides in the fact that an adequately large initial threshold will prevent the optimisation process from finding itself too early in a poor local extremum.
It is shown in practice, that the Threshold Accepting method delivers astonishingly improved results, even compared with comparatively "modern" processes like "simulated annealing" (cf also Dueck et al.), at clearly minimized calculation costs.